#define _CRT_SECURE_NO_WARNINGS 1

//链表分割(利用哨兵位的方法)
// 1，分别创建哨兵位存储大小等于x的链表头链表和尾链表
// 2，将小于x的尾链表指向大等于x的头链表，记得处理大等于x的尾链表
// 3，释放空间
//ListNode* partition(ListNode* pHead, int x) {
//    struct ListNode* lhead = NULL, * ltail = NULL;
//    lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));//创建哨兵位
//    struct ListNode* ghead = NULL, * gtail = NULL;
//    ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* cur = pHead;
//    while (cur)
//    {
//        if (cur->val < x)
//        {
//            ltail->next = cur;
//            ltail = ltail->next;
//        }
//        else
//        {
//            gtail->next = cur;
//            gtail = gtail->next;
//        }
//        cur = cur->next;
//    }
//    ltail->next = ghead->next;//将两个链表连接起来
//    gtail->next = NULL;//防止链表成环，尾插不改变结点的next
//    struct ListNode* head = lhead->next;
//    free(lhead);
//    free(ghead);
//    return head;
//}

//相交链表(相交后的链表相等)
// 1，依次遍历得到两个链表的长度
// 2，长度相减求绝对值得到之间的差距gap
// 3，判断长链表，并让其先走gap步
// 4，判断（Longlist != shortlist）为假则找到相交链表并返回
//struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//struct ListNode* curA = headA, * curB = headB;
//int lenA = 1, lenB = 1;
//while (curA)
//{
//    curA = curA->next;
//    lenA++;
//}
//while (curB)
//{
//    curB = curB->next;
//    lenB++;
//}
//if (curA != curB)
//{
//    return NULL;
//}
//int gap = abs(lenA - lenB);
//struct ListNode* Longlist = headA, * shortlist = headB;
//if (lenA < lenB)
//{
//    Longlist = headB;
//    shortlist = headA;
//}
//while (gap--)
//{
//    Longlist = Longlist->next;
//}
//while (Longlist != shortlist)
//{
//    Longlist = Longlist->next;
//    shortlist = shortlist->next;
//}
//return Longlist;
//}

//环形链表
// 利用快慢指针进行比较，若链表是环形链表，则快指针会追上慢指针，；反之则解释循环返回false
//bool hasCycle(struct ListNode *head) {
//struct ListNode* fast = head, * slow = head;
//while (fast && fast->next) //偶数个和奇数个
//{
//    fast = fast->next->next;
//    slow = slow->next;
//    if (slow == fast)
//    {
//        return true;
//    }
//}
//return false;
//}

// 链表的回文结构
// 1，找到中间链表
// 2，将后半段链表逆置
// 3，用头链表与逆置后的链表进行比较
// 相同继续，不同返回false
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* head) {
//        struct ListNode* fast = head, * slow = head;
//        struct ListNode* cur = head;
//        找链表中间位置
//        while (fast->next && fast)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//        }
//        //此时slow为中间值
//        将后半段链表逆制
//        struct ListNode* newnode = NULL;
//        while (slow)
//        {
//            struct ListNode* next = slow->next;
//            slow->next = newnode;
//            newnode = slow;
//            slow = next;
//        }
//        //此时newnode为中间值逆制后的头结点
//        while (cur && newnode)
//        {
//            if (cur->val != newnode->val)
//            {
//                return false;
//            }
//            cur = cur->next;
//            newnode = newnode->next;
//        }
//        return true;
//    }
//};